// 并查集
class UFSet
{
public:
	UFSet(size_t n) :_uft(n, -1) {}

    void Union(int x1, int x2)
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

        if (abs(_uft[root1]) < abs(_uft[root2]))
            swap(root1, root2);

        _uft[root1] += _uft[root2];
        _uft[root2] = root1;
    }


    int FindRoot(int x)
    {
        int root = x;
        while (_uft[root] >= 0)
        {
            root = _uft[root];
        }

        int parent = x;
        int tmp = 0;
        while (_uft[parent] >= 0)
        {
            tmp = _uft[parent];
            _uft[parent] = root;
            parent = tmp;
        }

        return root;
    }

	size_t SetSize()
	{
		size_t n = 0;
		for (size_t i = 0; i < _uft.size(); i++)
		{
			if (_uft[i] < 0) n++;
		}
		return n;
	}

private:
	vector<int> _uft;
};
